package suanfa;
import java.util.Arrays;

public class QuickSort2Ways {
	private QuickSort2Ways(){}
	public static int  partition(Comparable[] arr,int l,int r){
		swap(arr,l,(int)(Math.random()*(r-l+1))+l);
		Comparable v=arr[l];
		int j=r;
		int i=l+1;
		while(true){
			while(i<=r&&arr[i].compareTo(v)<0)i++;
			while(j>=l+1&&arr[j].compareTo(v)>0)j--;
			if(i>=j)
				break;
			swap(arr,i,j);	
			i++;
			j--;
		}
		swap(arr,l,j);
		return j;
	}
	public static void sort(Comparable[] arr,int l,int r){
		if(r-l<=15){
			InsertionSort.sort(arr, l, r);
			return;
		}
		int p=partition(arr,l,r);
		sort(arr,l,p-1);
		sort(arr,p+1,r);
	}
	public static void sort(Comparable[] arr){
		int n=arr.length;
		sort(arr,0,n-1);
	}
	public static  void swap(Comparable[] arr,int i,int j){
		Comparable t=arr[i];
		arr[i]=arr[j];
		arr[j]=t;
		}
	
	public static void main(String[] args) {
		int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("suanfa.QuickSort2Ways", arr);

        return;

	}

}
